package com.cat.graphTheory;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/min-cost-to-connect-all-points/
 * @create 2025/9/24 20:04
 * @since JDK17
 */

public class Solution32 {
    int[] f;
    int ans, cnt;
    int find(int x) {
        if (x != f[x]) {
            f[x] = find(f[x]);
        }
        return f[x];
    }

    void merge(int x, int y, int val) {
        int fx = find(x), fy = find(y);
        if (fx != fy) {
            f[find(x)] = find(y);
            ans += val;
            cnt--;
        }
    }

    int get(int[][] p, int x, int y) {
        return Math.abs(p[x][0] - p[y][0]) + Math.abs(p[x][1] - p[y][1]);
    }

    public int minCostConnectPoints(int[][] points) {
        int n = points.length;
        f = new int[n];
        this.cnt = n;
        for (int i = 0; i < n; i++) {
            f[i] = i;
        }
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                list.add(new int[]{i, j, get(points, i, j)});
            }
        }
        list.sort((a, b) -> a[2] - b[2]);
        for (int[] e : list) {
            merge(e[0], e[1], e[2]);
            if (cnt == 0) {
                break;
            }
        }

        return ans;
    }
}
